package sol.leetcode;

import def.TreeNode;

/**
 * Construct Binary Tree from Inorder and Postorder Traversal
 */
public class Issue106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;
        return buildTree(inorder, 0, postorder, 0, len);
    }

    public TreeNode buildTree(int[] inorder, int istart, int[] postorder, int pstart, int len) {
        if (len == 0)
            return null;
        if (len == 1)
            return new TreeNode(inorder[istart]);

        int rootVal = postorder[pstart + len - 1];
        int rootIdx = -1;
        for (int i = istart; i < istart + len; ++i)
            if (inorder[i] == rootVal)
                rootIdx = i;
        int lSize = rootIdx - istart;//左子树长度
        int rSize = len - lSize - 1;//右子树长度

        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(inorder, istart, postorder, pstart, lSize);
        root.right = buildTree(inorder, istart + lSize + 1, postorder, pstart + lSize, rSize);

        return root;
    }

    public static void main(String[] args) {
        int[] inorder = {1, 3, 2};
        int[] postorder = {3, 2, 1};
        Issue106 sol = new Issue106();
        TreeNode root = sol.buildTree(inorder, postorder);

        System.out.println(root.val);
    }
}
